As known, Forward Error Correction (FEC) is a technique for detecting and possibly correcting errors in digital data transmissions between network elements of a digital communication network, e.g. a Wavelength Division Multiplexing (WDM) communication network.
According to FEC, at the transmitting side the digital data to be transmitted are encoded using an error correcting code which adds redundancy. At the receiving side, the redundancy is used to detect, and possibly to correct, errors in the original data.
Different types of error correcting codes are known, including block codes and convolutional codes. In particular, in block codes the digital data to be transmitted are divided into fixed-size blocks of k message symbols and each block is separately encoded into a respective codeword of n symbols by adding n-k redundancy symbols. In general, each symbol is formed by one or more bits. Herein after, for simplicity, it is assumed that each symbol comprises a single bit, which may take the value 0 or 1.
A block code is typically defined by a set of rules for calculating the n-k redundancy bits starting from the k message bits. For instance, in parity-check codes, each one of the n-k redundancy bits is calculated as the parity (namely, the modulo-2 addition) of a certain subset of the k message bits (and therefore is also termed herein after “parity bit”). Each rule corresponds to a respective parity check, which basically provides for checking whether the modulo-2 addition of the parity bit and the subset of the k message bits used for calculating it is equal to zero. A codeword is valid only if all the parity checks are satisfied.
A parity-check code may be also expressed in the form of a binary matrix (also termed parity-check matrix) with n-k rows corresponding to the n-k parity checks and n columns corresponding to the n bits of the codeword.
Amongst the parity-check codes, Low-Density Parity-Check (LDPC) codes are known and presently widely used in WDM communication networks. LDPC codes have parity-check matrixes that contain only a very small number of non-zero entities (namely, they are sparse matrixes). The sparseness of the parity-check matrix guarantees both a decoding complexity which increases only linearly with the code length and a minimum distance which also increases linearly with the code length.
LDPC codes are often represented in graphical form by a Tanner graph. A Tanner graph basically consists of two columns of nodes: a first column of n nodes called “variable nodes” and a second column of n-k nodes called “check nodes”. Each variable node corresponds to a respective codeword bit (either a message bit or a parity bit), while each check node corresponds to a respective parity check. In the graph, codeword bits included in a certain parity check have their variable nodes joined to the check node of that parity check. This provides an intuitive graphical representation of the parity checks that define the LDPC code.
LDPC codes are typically decoded using iterative algorithms known as “message-passing algorithms”, in that variable nodes and check nodes act like state machines iteratively exchanging messages and updating their states. Different types of message-passing algorithms are known, which differ for the content of the exchanged messages and for the processing carried out at variable nodes and check nodes. A particular class of message-passing algorithms is that of the so-called “belief propagation algorithms”, wherein the messages exchanged between a variable node corresponding to a certain codeword bit and the neighboring check nodes comprise probabilities that the codeword bit has the value 1 or 0.
The probability of a codeword bit being equal to 1 or 0 is often expressed as a so-called “log likelihood ratio” (or, briefly, LLR), namely:
                              LLR          =                                    log              10                        ⁡                          (                                                p                  ⁡                                      (                    0                    )                                                                    p                  ⁡                                      (                    1                    )                                                              )                                      ,                            [        1        ]            where p(0) and p(1) are the probabilities that the codeword bit is equal to 0 and to 1, respectively. Since the values of p(0) and p(1) are comprised between 0 and 1, it is apparent that an LLR>0 indicates that the codeword bit is more probably 0 than 1, while an LLR<0 indicates that the codeword bit is more probably 1 than 0. The higher the modulus of LLR, the higher the certainty of the decision. Besides, LLR=0 indicates that the probabilities that the codeword bit is 1 or 0 are the same.
A particular belief propagation algorithm using the log likelihood ratio LLR is the so-called “sum-product algorithm”. According to the sum-product algorithm, each variable node firstly receives as input an a priori probability (in terms of LLR) of its codeword bit, which is typically provided thereto by a preceding component of the receiver, e.g. the demodulator. Then, the variable node calculates an a posteriori probability (in terms of LLR) of its codeword bit, which takes into account both the a priori probability and extrinsic information provided by the neighboring check nodes. The extrinsic information relating to the codeword bit (and therefore the whole a posteriori probability) is refined (and therefore made more accurate) by check node processing at each iteration of the algorithm, namely at each exchange of messages between the variable node and the neighbor check node(s). After a predefined number of iterations, the algorithm ends and the final value of the a posteriori probability is used for taking a hard decision on (namely, assigning the value 0 or 1 to) the codeword bit.
From the implementation point of view, a message-passing algorithm is typically implemented by a FEC decoder comprising a number of cascaded decoding blocks, one per each iteration of the algorithm. Each decoding block receives from the preceding block the a posteriori probabilities or the extrinsic information calculated at the previous iteration, and calculates new, refined a posteriori probabilities or new, refined extrinsic information. The last decoding block then passes the a posteriori probabilities to a hard decision block, which takes a hard decision for each codeword bit (in case of LLRs, based on the sign of the last computed value of its LLR namely, the decided value is 0 if LLR>0 and 1 if LLR<0).
Besides LDPC codes, turbo codes are also known, which provide comparable performance. Turbo codes typically provide three blocks of bits: a first block is formed by the original k message bits to be transmitted, a second block is formed by n/2 first parity bits computed using a convolutional error correcting code on the k message bits, and a third block is formed by n/2 second parity bits computed using the same convolutional error correcting code on a permutation of the k message bits. Thus, two redundant (but different) blocks of parity bits are transmitted with the k message bits.
C. Berrou et al. “Near Optimum Error Correcting Coding and Decoding: Turbo Codes”, IEEE Transactions on Communications, Vol. 44, No. 10, October 1996 describes a family of convolutional turbo codes built from a particular concatenation of two recursive systematic codes. Decoding uses an iterative process in which each component decoder takes advantage of the work of the previous step, with the aid of extrinsic information.
U.S. Pat. No. 6,654,927 describes an iterative error-correction for turbo decoding which uses at least two parallel decoding processes and comprises two iterations from which the decoded data is obtained by combining decoded elements of the iterations. Also, for each iteration, an intermediate decoded data element is multiplied by a scaling factor based upon parameters of the previous decoded data element block and is used on the next decoding iteration.